﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace zielonka.co.uk.extensions.system.collections
{
    // Description: Shuffles a list, see also zielonka.co.uk.extensions.System.Security.Cryptography
    // it has a true random shuffle
    /*
         Usage (assuming that the list is sorted by Id) :
            var item = list.BinarySearch(i => i.Id, 42);
     
        The fact that it throws an InvalidOperationException may seem strange, but that's what Enumerable.First does when there's no matching item.
      */

    public static partial class ListExtensions
    {
        public static T BinarySearch<T, TKey>(this IList<T> list, Func<T, TKey> keySelector, TKey key)
            where TKey : IComparable<TKey>
        {
            int min = 0;
            int max = list.Count;
            int index = 0;
            while (min < max)
            {
                int mid = (max + min)/2;
                T midItem = list[mid];
                TKey midKey = keySelector(midItem);
                int comp = midKey.CompareTo(key);
                if (comp < 0)
                {
                    min = mid + 1;
                }
                else if (comp > 0)
                {
                    max = mid - 1;
                }
                else
                {
                    return midItem;
                }
            }
            if (min == max &&
                keySelector(list[min]).CompareTo(key) == 0)
            {
                return list[min];
            }
            throw new InvalidOperationException("Item not found");
        }
    }
}
